package com.fml.easy;

import java.util.HashMap;
import java.util.Map;

/**
 * 给你一个非递减的 有序 整数数组，已知这个数组中恰好有一个整数，它的出现次数超过数组元素总数的 25%。
 *
 * 请你找到并返回这个整数
 */
public class Demo02 {

    public int findSpecialInteger(int[] arr) {
        int a = 0;
        int times = arr.length / 4;
        Map<Integer, Integer> map = new HashMap();
        for (int i : arr) {
            if (!map.containsKey(i)) {
                map.put(i, 1);
            }
            if (map.get(i) > times) {
                a = i;
                break;
            }
            map.put(i, map.get(i) + 1);

        }

        return a;
    }


    public static void main(String[] args) {
        int[] arr = {1, 1, 1, 1, 1, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 12, 12, 12};
        System.out.println(findSpecialInteger1(arr));
    }
    public static int findSpecialInteger1(int[] arr) {
        int a = arr[0];
        int tempTimes = 1;
        int times = arr.length / 4 ;
        for (int i = 1; i < arr.length; i++) {
            if (arr[i] == arr[i - 1]) {
                tempTimes++;
            } else {
                a = arr[i];
                tempTimes = 1;

            }
            if (times <= tempTimes) {
                break;
            }
        }
        return a;
    }

    public int findSpecialInteger2(int[] arr) {
        int times = arr.length / 4 + 1;
        for (int i = 0; i < arr.length; i++) {

            if (arr[i] == arr[i + times]) {
                return arr[i];
            }
        }
        return -1;
    }
}
